\section{Optimizations}

Inferred type information can be used to remove runtime type
discrimination (typeq instructions, as described in \refSec{sec-hir})
from the code. If the type of an input to typeq is inferred, it could
be that only one branch of the typeq is ever taken, and thus the typeq
itself can be removed.

For example, consider the code:

\begin{verbatim}
(if (consp item)
    (let ((key (car item))
          (value (cdr item)))
      ...)
    ...)
\end{verbatim}

This would initially appear in HIR as \refFig{fig-unoptimized},
with the \texttt{consp} being inlined as a \texttt{typeq}. The
\texttt{car} and \texttt{cdr} calls involve two additional typeqs
each, though they are obviously redundant.

\begin{figure}
\begin{center}
\inputfig{fig-unoptimized-hir.pdf_t}
\end{center}
\caption{\label{fig-unoptimized}
Unoptimized HIR fragment.}
\end{figure}

The inferencer can determine from the earliest typeq that ``item'' must
be a cons in the first if branch. The other four typeqs can then be
eliminated, resulting in the HIR in \refFig{fig-optimized}. The
semantics of the original program are preserved, but it is implemented
without unnecessary branching.

\begin{figure}
\begin{center}
\inputfig{fig-optimized-hir.pdf_t}
\end{center}
\caption{\label{fig-optimized}
HIR fragment after removing redundant typeqs.}
\end{figure}

In the Clasp implementation of Common Lisp, this optimization has been
tested to reduce the execution time (over ten million iterations) of a
Fibonacci function by ~56\%.
